import java.util.Arrays;
import java.util.Scanner;

public class Demo {
    public static void func1(int[] array){
        array=new int[10];
    }
    public static void func2(int[] array){
        array[0]=10;
    }

    public static void main1(String[] args) {
        int[] arr={1,2,3,4,5};
        System.out.println("调用方法前"+ Arrays.toString(arr));
        func2(arr);
        System.out.println("调用方法后"+ Arrays.toString(arr));
    }




    /*描述
    读入一个字符串str，输出字符串str中的连续最长的数字串
    输入描述：
    个测试输入包含1个测试用例，一个字符串str，长度不超过255。
    输出描述：
    在一行内输出str中里连续最长的数字串。
    示例1
    输入：
    abcd12345ed125ss123456789

    输出：
    123456789

    思路---遍历字符串，使用cur去记录连续的数字串，如果遇到不是数字字符，则表示一个连续的数字串结束了，则将
    数字串跟之前的数字串比较，如果更长，则更新更长的数字串更新到res*/
    public static void main2(String[] args) {
        Scanner scan=new Scanner(System.in);
        String str=scan.nextLine();
        String cur="";
        String ret="";
        int i=0;
        for(;i<str.length();i++){
            char ch=str.charAt(i);
            if(ch>='0'&&ch<='9'){
                cur=cur+ch+"";
            }else{
                if(cur.length()>ret.length()){
                    ret=cur;
                }
                else{
                    cur="";
                }
            }
        }
        if(i==str.length()&&cur.length()>ret.length()){
            ret=cur;
        }
        System.out.println(ret);
    }





   /* 描述
    给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
    例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

    数据范围：n≤50000，数组中元素的值 0≤val≤10000
    要求：空间复杂度：O(1)，时间复杂度 O(n)
    输入描述：
    保证数组输入非空，且保证有解
    示例1
    输入：
    [1,2,3,2,2,2,5,4,2]

    返回值：
    2*/

    //思路一：先对这个数组排序，找到中间的数字x，再遍历这个数组，看这个x出现的次数是否符合题意

    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        if(numbers==null||numbers.length==0){
            return 0;
        }
        Arrays.sort(numbers);
        int len=numbers.length;
        int mid=numbers[len/2];
        int count=0;
        for(int i=0;i<len;i++){
            if(numbers[i]==mid){
                count++;
            }
        }
        if(count>len/2){
            return mid;
        }
        return 0;
    }


    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int[] arr=new int[n];
        int tmp=0;
        int count=0;
        for (int i = 0; i < arr.length; i++) {
            arr[i]=scan.nextInt();
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[i] > arr[j]) {
                    tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
        int mid=arr[n/2];
        for(int i=0;i<arr.length;i++){
            if(arr[i]==mid){
                count++;
            }
        }
        if(count>arr.length/2){
            System.out.println(mid);
        }
    }


    //思路二:如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数
    //那么如果存在众数，最后留下的数肯定是众数，当然，不确定这个数组是否有众数，最后也需要判断一下
    //众数：就是出现次数超过数组长度一半的那个数字
    public int MoreThanHalfNum_Solution1 (int[] numbers) {
        // write code here
        if(numbers==null||numbers.length==0){
            return 0;
        }
        int result = numbers[0];
        int times = 1;//次数
        int count=0;
        int len = numbers.length;
        for (int i = 1; i < len; i++) {
            if (times != 0) {
                if (numbers[i] != result) {
                    times--;
                } else {
                    times++;
                }
            }else{
                //更新result的值为当前元素，并置次数为1
                result=numbers[i];
                times=1;
            }
        }
        //判断result是否符合条件，即出现次数大于数组长度的一半
        for(int i=0;i<len;i++){
            if(numbers[i]==result){
                count++;
            }
        }
        if(count>len/2){
            return result;
        }
        return 0;
    }


}
